Date: Mon, 25 Nov 1996 22:14:17 GMT
Server: NCSA/1.5.2
Last-modified: Mon, 28 Oct 1996 19:18:09 GMT
Content-type: text/html
Content-length: 3833

<html>
<head>
<Title>Home Page for Martin Farach</Title>
</head>
<body>

<HR>
<H1>Martin Farach</H1>
<!WA0><img src=http://www.cs.rutgers.edu/~farach/mf72.gif>
<HR>

<address>
  Assistant Professor<br>
  <!WA1><a href="http://www.cs.rutgers.edu">Department of Computer Science</a><br>
  <!WA2><a href="http://www.rutgers.edu">Rutgers University</a><br>
  Piscataway, NJ 08855<br>
  USA
  <p>

  Phone: (908) 445-6424<br>
  Fax: (908) 445-5530/0537<br>
  <p>

Email:  <!WA3><A HREF="mailto:farach@cs.rutgers.edu">farach@cs.rutgers.edu</A><P>

Office: <!WA4><A
href="http://athos.rutgers.edu/pub/colloquia/directions-to-Hill-Center">
Hill 448</A>
</address>
<p>

<HR>

My interests include analysis of algorithms and computational
molecular biology. <P>


<A NAME="publications"><H2> Selected Publications: </H2></A>
<ul>
  <H3> <li> String Matching</H3>
       <UL>
	 <LI><!WA5><A HREF =
	 "ftp://cs.rutgers.edu/pub/farach/DynamicDictionary.ps.Z"> 
	      Dynamic Dictionary Matching</A> (JCSS V.49 pp. 208-222,
	      1994; see also FOCS '91) 
	 <LI><!WA6><A HREF = "ftp://cs.rutgers.edu/pub/farach/2dAlphaInd.ps.Z">
	      An Alphabet Independent Approach to Two Dimensional Pattern
	      Matching</A> (SICOMP V.23, 1994; see also STOC '92)
	 <LI><!WA7><A HREF =
	 "ftp://cs.rutgers.edu/pub/farach/RandomizedDictionary.ps.Z"> 
	      Efficient Randomized Dictionary Matching Algorithms</A>
	      (CPM '92) 
	 <LI><!WA8><A HREF = "ftp://cs.rutgers.edu/pub/farach/DynamicIndexing.ps.Z">
	      An Efficient Algorithm for Dynamic Text Indexing</A>
	      (SODA '94) 
	 <LI><!WA9><A HREF = "ftp://cs.rutgers.edu/pub/farach/LZ2-Matching.ps.Z">
	      Let Sleeping Files Lie:Pattern Matching in Z-compressed
	      Files</A> (To appear in JCSS; see also SODA '94) 
	 <LI><!WA10><A HREF = "ftp://cs.rutgers.edu/pub/farach/LZ1-Matching.ps.Z">
	      String Matching in Lempel-Ziv Compressed Strings</A>
	      (STOC '95)  
	 <LI><!WA11><A HREF = "ftp://cs.rutgers.edu/pub/farach/ParDict.ps.Z">
	      Optimal Parallel Dictionary Matching and Compression</A>
	      (SPAA '95)  
       </ul><p>
<h3>  <li> Phylogeny - Construction</h3>
       <ul>
	 <LI><!WA12><A HREF = "ftp://cs.rutgers.edu/pub/farach/Ultrametric.ps.Z">
	      A Robust Model for Finding Optimal Evolutionary
	      Trees</A> (Algorithmica, Special Issue on Computational
	      Biology, V.13, pp. 155-179, 1995; see also STOC '93) 
	 <LI><!WA13><A HREF = "ftp://cs.rutgers.edu/pub/farach/Additive.ps.Z">
	      On the Approximability of Numerical Taxonomy:
	      (Fitting Distances by Tree Metrics) </A> (SODA '96)
	 <LI><!WA14><A HREF = "ftp://cs.rutgers.edu/pub/farach/MLE.ps.Z">
	      Efficient Algorithms for Inverting Evolution </A> (STOC '96)
	 <LI><!WA15><A HREF = "ftp://cs.rutgers.edu/pub/farach/NumTaxExp.ps.Z">
	      Numerical Taxonomy on Data: Experimental Results </A>
	      (SODA '97 and RECOMB '97)
       </ul><p>

<h3>  <li> Phylogeny - Comparison</h3>
       <ul>
	 <LI><!WA16><A HREF = "ftp://cs.rutgers.edu/pub/farach/UMAST.ps.Z">
	      Fast Comparison of Evolutionary Trees </A> (Information
	      and Computation, to appear; see also SODA '94) 
	 <LI><!WA17><A HREF = "ftp://cs.rutgers.edu/pub/farach/RMAST.ps.Z">
	      Optimal Evolutionary Tree Comparison by Sparse Dynamic
	      Programming </A> (FOCS '94; also to appear in SICOMP) 
	 <LI><!WA18><A HREF = "ftp://cs.rutgers.edu/pub/farach/KMAST.ps.Z">
	      On the Agreement of Many Trees</A> (ESA '95; also to
	      appear in IPL).  Available in <!WA19><A
	      HREF="ftp://onyx.si.edu/paup"> PAUP</A> software package.
       </ul><p>

<h3>   <li> Others</h3>
       <ul>
	 <LI><!WA20><A HREF =
	 "ftp://cs.rutgers.edu/pub/farach/SpliceJunction.ps.Z"> 
	      On the Entropy of DNA: Algorithms and Measurements based
	      on Memory and Rapid Convergence </A> (SODA '95) 
	 <LI><!WA21><A HREF ="ftp://cs.rutgers.edu/pub/farach/CDM.ps.Z"> 
	      The Structure of Circular Decomposable Metrics </A> (ESA '96)
       </ul><p>
       </UL>
</ul>

<P>

</MENU>

